1. Technical Field of the Present Invention
The present invention generally relates to the design of integrated circuits, and more specifically, to the placement of cells within the design.
2. Description of Related Art
Integrated circuits have a large number of electronic components (millions of transistors) and are fabricated using several layers of different materials placed on a silicon base or wafer. The design of an integrated circuit involves transforming a description of the electrical components into geometrical representations known as a layout. The layout has a set of planar geometric shapes in each of the various layers of materials.
The process of transforming the description of the electrical components into a layout is called the physical design. Physical design involves arranging elements, wires, and predefined cells on a fixed area. Due to the large number of components and the exacting details required by the fabrication process, physical design is not practical without the aid of computers. As a result, most phases of physical design use Computer Aided Design (CAD) tools.
The object of the physical chip design is to determine an optimal arrangement for devices residing on a plane and to find an efficient interconnection or routing scheme between the devices to obtain the desired functionality. Since space on the chip surfaces are at a premium, algorithms for this placement must use this space very efficiently in order to lower costs and improve yield. The arrangement of individual cells in an integrated circuit is known as cell placement.
Placement migration is the movement of cells within an existing placement to address a variety of post-placement design closure issues such as timing, routing congestion, signal integrity, and heat distribution. Any movement by the cells during placement migration must be performed so as to minimize the disruption to the original placement as little as possible.
A placement is considered “illegal” if cells overlap or fail to align with circuit rows. The term “legalization” is used to describe the process of taking an illegal placement and disrupting the layout to make it “legal” while minimizing any disruptions so as to preserve as near as possible the desired characteristics of the original illegal placement.
Existing techniques for performing legalization include network flow, heuristic ripple cell movement, dynamic programming, and single row optimization. Although these techniques accomplish the legalization of the cell placement, they do so at a cost that disrupts the original cell placement more than is optimally desired.
It would, therefore, be a distinct advantage to have a method and apparatus that implements a legalization technique in a more continuous manner than the prior art methods.